package com.LeetCode.dp.Array;

import org.junit.Test;

import java.util.Arrays;

/**
 * 平方数
 */
public class NumberSqure {

    public int numSquares(int n) {
        int sqrt_n = (int)Math.sqrt(n)+1;
        int[] sqrts = new int[sqrt_n];
        for(int i = 1; i<sqrt_n; i++){
            sqrts[i] = i * i;
        }

        int[] dp = new int[n+1];
        Arrays.fill(dp,Integer.MAX_VALUE);
        dp[0] = 0;
        for(int i = 1; i<=n; i++){
            for(int j = 1; j<sqrt_n; j++){
                if(i < sqrts[j]) break;
                dp[i] = Math.min(dp[i], dp[i - sqrts[j]] + 1);

            }
        }
        return dp[n];
    }

    @Test
    public void test(){
        System.out.println(numSquares(12));
    }
}
